package org.example.myleet.p1020;

import java.util.LinkedList;
import java.util.Queue;

public class Solution {

    private static final int[][] DIRECTIONS = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public int numEnclaves(int[][] grid) {
        int landCount = 0, m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                landCount += grid[i][j];
            }
        }
        boolean[][] visited = new boolean[m][n];
        //扫一次外圈四边，通过BFS方式找到所有和边界相连的陆地的数量，并减掉，剩下的就是飞地数量
        int r = m - 1, c = n - 1;
        for (int j = 0; j < n; ++j) {
            if (grid[0][j] == 1 && !visited[0][j]) {
                landCount -= bfsFindConnectedLand(grid, m, n, visited, 0, j);
            }
            if (grid[r][j] == 1 && !visited[r][j]) {
                landCount -= bfsFindConnectedLand(grid, m, n, visited, r, j);
            }
        }
        for (int i = 1; i < m - 1; ++i) {
            if (grid[i][0] == 1 && !visited[i][0]) {
                landCount -= bfsFindConnectedLand(grid, m, n, visited, i, 0);
            }
            if (grid[i][c] == 1 && !visited[i][c]) {
                landCount -= bfsFindConnectedLand(grid, m, n, visited, i, c);
            }
        }
        return landCount;
    }

    private int bfsFindConnectedLand(int[][] grid, int m, int n, boolean[][] visited, int r, int c) {
        int connectedLandCount = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{r, c});
        visited[r][c] = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                ++connectedLandCount;
                int[] point = queue.poll();
                for (int k = 0; k < 4; ++k) {
                    int r_ = point[0] + DIRECTIONS[k][0];
                    int c_ = point[1] + DIRECTIONS[k][1];
                    if (0 <= r_ && r_ < m && 0 <= c_ && c_ < n && !visited[r_][c_] && grid[r_][c_] == 1) {
                        queue.offer(new int[]{r_, c_});
                        visited[r_][c_] = true;
                    }
                }
            }
        }
        return connectedLandCount;
    }
}
